import java.util.ArrayDeque;
import java.util.Deque;

public class Tes {
}
class FrontMiddleBackQueue {
    private final Deque<Integer> left = new ArrayDeque<>();
    private final Deque<Integer> right = new ArrayDeque<>();

    private void balance(){
        if(left.size() > right.size()){
            right.addFirst(left.pollLast());
        }else if(right.size() > left.size() + 1){
            left.addLast(right.pollFirst());
        }
    }

    public FrontMiddleBackQueue() {

    }

    public void pushFront(int val) {
        left.addFirst(val);
        balance();
    }

    public void pushMiddle(int val) {
        if(left.size() < right.size()){
            left.addLast(val);
        }else{
            right.addFirst(val);
        }
    }

    public void pushBack(int val) {
        right.addLast(val);
        balance();
    }

    public int popFront() {
        if(right.isEmpty()){
            return -1;
        }
        int val = left.isEmpty()?right.pollFirst():left.pollFirst();
        balance();
        return val;
    }

    public int popMiddle() {
        if(right.isEmpty()){
            return -1;
        }
        if(left.size() == right.size()){
            return left.pollLast();
        }
        return right.pollFirst();
    }

    public int popBack() {
        if (right.isEmpty()) { // 整个队列为空
            return -1;
        }
        int val = right.pollLast();
        balance();
        return val;
    }
}
